#pragma once

// . Pthread implemented with Windows (Vista & Seven)sync primitives : 
//	http://locklessinc.com/articles/pthreads_on_windows/
//
// . About Windows sync primitives introduced with VISTA
//	http://msdn.microsoft.com/en-us/magazine/cc163405.aspx
//
// . Nb cores : 
//	http://stackoverflow.com/questions/150355/programmatically-find-the-number-of-cores-on-a-machine
//
// . A Must Read when you enter the world of lock-free / wait-free programming
// http://www.liblfds.org/wikipedia/images/9/99/Michael_-_Hazard_Pointers%3B_Safe_Memory_Reclaimation_for_Lock-Free_Objects.pdf

// From MSDN Docs : 
// On Xbox 360 the InterlockedXxx functions do not contain CPU memory barriers. 
// They prevent compiler reordering of reads and writes but not CPU reordering. 
// Therefore, in most cases when using InterlockedXxx functions on Xbox 360, you should precede or follow them with an __lwsync, 
// to make them a read-acquire or write-release barrier. 
// For convenience and for easier readability there are Acquire and Release versions of many of the InterlockedXxx functions. 
// These come with a built-in memory barrier. 
// For instance, InterlockedIncrementAcquire does an interlocked increment followed by an __lwsync memory barrier to give the full read-acquire functionality.
//
// [...]
//
//	Xbox 360 Performance
//
// The performance of synchronization instructions and functions on Xbox 360 will vary depending on what other code is running. Acquiring locks will take much longer if another thread currently owns the lock. InterlockedIncrement and critical section operations will take much longer if other threads are writing to the same cache line. The contents of the store queues can also affect performance. Therefore, all of these numbers are just approximations, generated from very simple tests:
//
// lwsync was measured as taking 33-48 cycles.
// InterlockedIncrement was measured as taking 225-260 cycles.
// Acquiring or releasing a critical section was measured as taking about 345 cycles.
// Acquiring or releasing a mutex was measured as taking about 2350 cycles.
//
//	Windows Performance
//
// However, even some measurements generated from very simple tests are helpful:
//
// MemoryBarrier was measured as taking 20-90 cycles.
// InterlockedIncrement was measured as taking 36-90 cycles.
// Acquiring or releasing a critical section was measured as taking 40-100 cycles.
// Acquiring or releasing a mutex was measured as taking about 750-2500 cycles.
//
// These tests were done on Windows XP on a range of different processors. The short times were on a single-processor machine, and the longer times were on a multi-processor machine.
//
// [...]
//
// Lockless algorithms are not guaranteed to be faster than algorithms that use locks. 
// You should check to see if locks are actually causing you problems before trying to avoid them, and you should measure to see if your lockless code actually improves performance.

#include <list>
#include <vector>
#include <map>
#include <assert.h>
#include <algorithm>
#include <intrin.h>
//#include <unistd.h>


#define CACHE_LINE_SIZE		64 // on Intel Core 2, i7, AMD Athlon X2, iPhone 3GS
// CACHE_LINE_SIZE		128 // on Xbox360, PS3
// CACHE_LINE_SIZE		32	// on Wii

#define ENABLE_PROFILING	1

#define MSG(...)						fprintf(stderr,__VA_ARGS__)

//extern volatile bool	gbWaitOnAssert = false;




#ifdef _DEBUG

	#define LOG(...)					fprintf(stderr,__VA_ARGS__)
	 
	#define MB_ASSERT( expr, ... ) \
		if( !(expr) ) {  \
			LARGE_INTEGER tick; QueryPerformanceCounter(&tick);\
			LOG( "\nASSERT! on Thread %d @ Tick %d:\n", Parallel::Thread::GetCurrentThreadID(), tick.QuadPart );\
			LOG( __VA_ARGS__ );	\
			LOG( "---> FILE = '%s'\n---> .LINE='%d'\n---> .FUNCTION='%s'\n", __FILE__ , __LINE__, __FUNCTION__);\
			__debugbreak();\
		}  

	#define MB_ERROR( expr, ... ) \
		if( !(expr) ) {  \
			LOG( "\nERROR ! on Thread %d :\n", Parallel::Thread::GetCurrentThreadID() );\
			LOG( __VA_ARGS__ );\
			LOG( "---> FILE = '%s'\n---> .LINE='%d'\n---> .FUNCTION='%s'\n", __FILE__ , __LINE__, __FUNCTION__);\
		}  

#else

	#define LOG(...)					fprintf(stderr,__VA_ARGS__)
	#define MB_ASSERT( expr, ... )    
	#define MB_ERROR( expr, ... ) 

#endif



//#define PROFILE_THREADS

#ifndef nullptr
#	define nullptr		NULL
#endif 
//typedef DWORD            INT32;


 
//////////////////////////////////////////////////////////////////////
//template <bool B>
//inline void STATIC_ASSERT_IMPL()
//{
//    // B will be true or false, which will implictly convert to 1 or 0
//    char STATIC_ASSERT_FAILURE[B] = {0};
//}

// NB : can be used in functions body only >.<
//#define STATIC_ASSERT(B)			STATIC_ASSERT_IMPL <(B)>()
//#define STATIC_ASSERT_MSG(B,MSG)	{STATIC_ASSERT_IMPL <(B)>();int StaticAssertMsg__##MSG;}

namespace Melting
{
	namespace Parallel
	{
	  template<int> struct StaticAssert;
	  template<>	struct StaticAssert<true> {};
	}
}// namespace Melting

#define STATIC_ASSERT(expr, msg)    { Parallel::StaticAssert<((expr) != 0)> _STATIC_ASSERT_##msg; (void)_STATIC_ASSERT_##msg; }


//////////////////////////////////////////////////////////////////////

#ifdef WIN32
 
	#define WIN32_LEAN_AND_MEAN             // Exclude rarely-used stuff from Windows headers 
    #include <windows.h>
    #include <tchar.h>
    #include <strsafe.h>
///////////////////////////
// TYPES
typedef unsigned char		UBYTE;


namespace Melting
{
namespace Parallel
{
    typedef DWORD			ThreadID;
    typedef HANDLE			ThreadHandle;
    typedef INT32			ThreadFunctionReturn;


// From MSDN docs : 
//	"When using InterlockedXxx on Xbox 360, use the Acquire and Release variants." -- because of read/write reorderding 
//	and 
//	"Itanium-based systems:  For performance-critical applications, use InterlockedIncrementAcquire or InterlockedIncrementRelease instead."

    extern "C"
    {
        // Make sure that the InterlockedXXX functions are generated as intrinsics:
        long        _InterlockedIncrement(long volatile *Addend);
        long        _InterlockedDecrement(long volatile *Addend);
        long        _InterlockedCompareExchange(long* volatile Dest, long Exchange, long Comperand);
        long long   _InterlockedCompareExchange64(long long volatile *Dest, long long Exchange, long long Comperand);
        long        _InterlockedExchange(long* volatile Target, long Value);
        long        _InterlockedExchangeAdd(long* volatile Addend, long Value);
    }
    FORCEINLINE INT32 AtomicIncrement( volatile INT32* _pValue )
    {
        return (INT32)_InterlockedIncrement( (long*)_pValue );
    }
    FORCEINLINE INT32 AtomicDecrement( volatile INT32* _pValue )
    {
        return (INT32)_InterlockedDecrement( (long*)_pValue );
    }
    FORCEINLINE INT32 AtomicAdd( volatile INT32* _pValue, INT32 _iAmount )
    {
        return (INT32)_InterlockedExchangeAdd( (long*)_pValue, (long)_iAmount );
    }
    FORCEINLINE INT32 AtomicSub( volatile INT32* _pValue, INT32 _iAmount )
    {
        return (INT32)_InterlockedExchangeAdd( (long*)_pValue, (long)-_iAmount );
    }
    FORCEINLINE INT32 AtomicSwap( volatile INT32* _pValue, INT32 _iExchange )
    {
        return (INT32)_InterlockedExchange( (long*)_pValue, (long)_iExchange );
    }
    FORCEINLINE INT32 AtomicCompareAndSwap( volatile INT32* _pDest, INT32 _iExchange, INT32 _iComperand )
    {
        return (INT32)_InterlockedCompareExchange( (long*)_pDest, (long)_iExchange, (long)_iComperand);
    }
    FORCEINLINE INT64 AtomicCompareAndSwap64bits( volatile INT64* _pDest, INT64 _iExchange, INT64 _iComperand )
    {
        return (INT64)_InterlockedCompareExchange64( (long long*)_pDest, (long long)_iExchange, (long long)_iComperand);
    }
}
}// namespace Melting
///////////////////////////
#else // LINUX
#include <pthread.h>
#include <signal.h>
#include <stdio.h>
///////////////////////////
typedef long				INT32;
typedef unsigned long		UINT32;
typedef long long			INT64;
typedef unsigned long long	UINT64;

namespace Melting
{
namespace Parallel
{
// TYPES
	typedef pid_t		ThreadID;
    typedef pthread_t   ThreadHandle;
    typedef void*       ThreadFunctionReturn;

    #define FORCEINLINE inline
    FORCEINLINE INT32 AtomicIncrement( volatile INT32* _pValue )
    {
        return (INT32)__sync_fetch_and_add( (long*)_pValue, (long) 1 );
    }
    FORCEINLINE INT32 AtomicDecrement( volatile INT32* _pValue )
    {
        return (INT32)__sync_fetch_and_sub( (long*)_pValue, (long) 1 );
    }
    FORCEINLINE INT32 AtomicAdd( volatile INT32* _pValue, INT32 _iAmount )
    {
        return (INT32)__sync_fetch_and_add( (long*)_pValue, (long)_iAmount );
    }
    FORCEINLINE INT32 AtomicSub( volatile INT32* _pValue, INT32 _iAmount )
    {
        return (INT32)__sync_fetch_and_sub( (long*)_pValue, (long)_iAmount );
    }
    FORCEINLINE INT32 AtomicSwap( volatile INT32* _pValue, INT32 _iExchange )
    {
        return (INT32)__sync_lock_test_and_set( (long*)_pValue, (long)_iExchange );
    }
    FORCEINLINE INT32 AtomicCompareAndSwap( volatile INT32* _pDest, INT32 _iExchange, INT32 _iComperand )
    {
        return (INT32)__sync_val_compare_and_swap( (long*)_pDest, (long)_iComperand, (long)_iExchange);
    }
//type __sync_fetch_and_add (type *ptr, type value);
//long _InterlockedExchangeAdd(
//   long volatile * Addend,
//   long Value
//);
//type __sync_fetch_and_sub (type *ptr, type value);
//type __sync_fetch_and_or (type *ptr, type value);
//long _InterlockedOr(
//   long volatile * Value,
//   long Mask
//);
//type __sync_fetch_and_and (type *ptr, type value);
//long _InterlockedAnd(
//   long volatile * value,
//   long mask
//);
//type __sync_fetch_and_xor (type *ptr, type value);
//long _InterlockedXor(
//   long volatile * Value,
//   long Mask
//);
//type __sync_fetch_and_nand (type *ptr, type value);
//type __sync_add_and_fetch (type *ptr, type value);
//type __sync_sub_and_fetch (type *ptr, type value);
//type __sync_or_and_fetch (type *ptr, type value);
//type __sync_and_and_fetch (type *ptr, type value);
//type __sync_xor_and_fetch (type *ptr, type value);
//type __sync_nand_and_fetch (type *ptr, type value);
//type __sync_val_compare_and_swap (type *ptr, type oldval type newval);
//long _InterlockedCompareExchange(
//   long volatile * Destination,
//   long Exchange,
//   long Comparand
//);
//type __sync_lock_test_and_set (type *ptr, type value);
//long _InterlockedExchange(
//   long * Target,
//   long Value
//);
}
}// namespace Melting
///////////////////////////
#endif
namespace Melting
{
namespace Parallel
{
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    FORCEINLINE void MemoryBarrier( void )
    {
    #ifdef WIN32
        ::MemoryBarrier();
    #elif POWERPC
        __lwsync();
    #else // LINUX
        __sync_synchronize();
    #endif
    }
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
    FORCEINLINE void Sleep( UINT32 _uiTime )
    {
    #ifdef WIN32
        ::Sleep( _uiTime );
    #else // LINUX
        sleep( _uiTime );
    #endif
    }
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
    FORCEINLINE void SwitchThread( void )
    {
        Sleep( 0 );
    }

	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	FORCEINLINE void YieldProcessor( void )
	{
    #ifdef WIN32
        ::YieldProcessor();
    #else // LINUX
        pthread_yield();
    #endif		
	} 
}
}// namespace Melting


#ifdef WIN32
#ifndef __FINALROM
#	if defined(WIN32)

#		ifndef MEASURE_START
#			define	MEASURE_START(_strName) 						LARGE_INTEGER start##_strName, stop##_strName, freq##_strName;	\
																	float fDuration##_strName;			\
																	QueryPerformanceFrequency(&freq##_strName);	\
																	QueryPerformanceCounter(&start##_strName);
#		endif

#		ifndef MEASURE_STOP
#			define	MEASURE_STOP(_strName) 							QueryPerformanceCounter(&stop##_strName);								\
																	fDuration##_strName = float(stop##_strName.QuadPart - start##_strName.QuadPart) / freq##_strName.QuadPart ;
#		endif
													
#		ifndef MEASURE_STOP_LOG		
#			define	MEASURE_STOP_LOG(_strName,_strMsg,_fMinTime) 	MEASURE_STOP(_strName);\
																	if( _fMinTime < fDuration##_strName ){	LOG( _strMsg##" :: Measure of '%s' is %f s\n", #_strName, fDuration##_strName );}
#		endif

#		ifndef GET_MEASURE
#			define	GET_MEASURE(_strName)							fDuration##_strName
#		endif

#	endif

#else
#	ifndef MEASURE_START
#		define	MEASURE_START(_strName)								do { } while (0)
#	endif	

#	ifndef MEASURE_STOP
#		define	MEASURE_STOP(_strName) 								do { } while (0)
#	endif	

#	ifndef MEASURE_STOP_LOG
#		define	MEASURE_STOP_LOG(_strName,_strMsg,_ulMinTime) 		do { } while (0)
#	endif	

#	ifndef GET_MEASURE
#		define	GET_MEASURE(_strName)								
#	endif	
#endif
#else // LINUX

#include <sys/time.h>
#       define  INIT_MEASURE_SYSTEM()                    {  timespec tS;    \
															tS.tv_sec = 0;  \
                                                            tS.tv_nsec = 0; \
                                                            clock_settime(CLOCK_PROCESS_CPUTIME_ID, &tS);}
// TODO : consider using		int clock_getres(clockid_t clock_id, struct timespec *res);
// TODO : consider using		CLOCK_THREAD_CPUTIME_ID 
#       define  MEASURE_START()								timespec timer1;               \
															double fDuration;               \
															clock_gettime( CLOCK_REALTIME, &timer1 );

#       define  MEASURE_STOP()								timespec timer2; \
															clock_gettime( CLOCK_REALTIME, &timer2 );\
															fDuration = double( (double) (timer2.tv_sec - timer1.tv_sec) + ((double) (timer2.tv_nsec - timer1.tv_nsec)) / 1000000000.0 );

#       define  MEASURE_STOP_LOG(_strMsg,_fMinTime)         MEASURE_STOP() \
                                                        /*if( _fMinTime < fDuration )    */{ printf( _strMsg );printf( " :: Measure is %f s\n", fDuration );}
//                                                        if( _fMinTime < fDuration )    printf( _strMsg ## " :: Measure is %f s\n", fDuration );

#       define  GET_MEASURE()							fDuration
/*
#else // LINUX
#include <sys/time.h>
#       define  MEASURE_START()                          timespec timer1;               \
                                                        double fDuration;               \
                                                        clock_gettime( CLOCK_REALTIME, &timer1 );
#       define  MEASURE_STOP()                           timespec timer2; \
                                                        clock_gettime( CLOCK_REALTIME, &timer2 );\
                                                        fDuration = double( (double) (timer2.tv_sec - timer1.tv_sec)  + (double) (timer2.tv_nsec - timer1.tv_nsec) / 1000000.0 );
#        define    MEASURE_STOP_LOG(_strMsg,_fMinTime)         MEASURE_STOP() \
                                                        if( _fMinTime < fDuration )    { printf( _strMsg );printf( " :: Measure is %f s\n", fDuration );}
//                                                        if( _fMinTime < fDuration )    printf( _strMsg ## " :: Measure is %f s\n", fDuration );
  */
#endif

inline UINT32 GetNumberOfBitsSet( UINT32 _iValue )
{
	// accumulates the total bits set in _iValue
	UINT32 iCount = 0; 

	while( 0 != _iValue )
	{
		// clear the least significant bit set
		_iValue &= _iValue - 1; 

		iCount++;
	}

	return iCount;
}

inline UINT32 GetNextPowerOfTwo( UINT32 _iValue )
{
	UINT32 iValue = _iValue - 1 ;

	iValue |= iValue >> 1;
	iValue |= iValue >> 2;
	iValue |= iValue >> 4;
	iValue |= iValue >> 8;
	iValue |= iValue >> 16;
	iValue++;

	return iValue;
}

/// Returns true if the _iValue is a power of two, or zero
inline bool IsPowerOfTwo( UINT32 _iValue )
{ 
	return 0 == (_iValue & ( _iValue - 1 ) );
}


#include "ThreadLocalStorage.h"
#include "Atomic.h"
//#include "AtomicCounter.h"
#include "RWLock.h"
#include "Mutex.h"
#include "SpinLock.h"
#include "ConditionVariable.h"
#include "Thread.h"

#include "Memory.h"
#include "Profiling.h"

#include "LockFreeQueue.h"
#include "LockFreeStack.h"
#include "Task.h"
#include "WorkerThread.h"
#include "TaskManager.h"



namespace Melting
{
namespace Parallel
{
	//--------------------------------------------------------------------------------------------------------------------
	//--------------------------------------------------------------------------------------------------------------------
	FORCEINLINE INT32 GetNbCores( void )
	{
		INT32 iNbCores;

    #ifdef WIN32
		SYSTEM_INFO sysinfo;
		GetSystemInfo( &sysinfo );

		iNbCores = sysinfo.dwNumberOfProcessors;

    #else // LINUX
        iNbCores = sysconf( _SC_NPROCESSORS_ONLN );

    #endif		

		MB_ASSERT( 0 < iNbCores, "Could not retrieve the number of logical cores\n" );

		return iNbCores;
	}
}
}// namespace Melting
